package _09_高频题;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class _253_会议室二 {

    // 分别排序
    public int roomCount(int[][] nums) {
        if (nums.length == 0) return 0;
        // 排序
        Arrays.sort(nums, Comparator.comparingInt(a -> a[0]));
        int[] begins = new int[nums.length];
        int[] ends = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            begins[i] = nums[i][0];
            ends[i] = nums[i][1];
        }
        int endIndex = 0;
        int count = 1;
        for (int begin : begins) {
            if (begin <= ends[endIndex]) {
                endIndex++;
            } else {
                count++;
            }
        }
        return count;
    }


    // 利用最小堆
    public int roomCount1(int[][] nums) {
        if (nums.length == 0) return 0;
        // 排序
        Arrays.sort(nums, Comparator.comparingInt(a -> a[0]));
        // 使用最小堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.offer(nums[0][1]);

        for (int i = 1; i < nums.length; i++) {
            if (heap.peek() >= nums[i][0]) {
                // 最小元素出队
                heap.remove();
            }
            // 元素入队
            heap.offer(nums[i][1]);
        }
        return heap.size();
    }

}
